软考真题
第4题

阅读下列说明和C代码,回答问题1和问题2,将解答填入答题纸的对应栏内。

【说明】
某公司购买长钢条,将其切割后进行出售。切割钢条的成本可以忽略不计,钢条的长度为整英寸。已知价格表p,其中pi(i=1,2,...,m)表示长度为i英寸的钢条的价格。现要求解使销售收益最大的切割方案。

求解此切割方案的算法基本思想如下:

假设长钢条的长度为n英寸,最佳切割方案的最左边切割段长度为i英寸,则继续求解剩余长度为ni 英寸钢条的最佳切割方案。考虑所有可能的i,得到的最大收益rn对应的切割方案即为最佳切割方案。rn的递归定义如下:

rn =max1≤ i n(pi +rn-i)

对此递归式,给出自顶向下和自底向上两种实现方式。

【C代码】

/* 常量和变量说明
​
n:长钢条的长度
p[]:价格数组
*/
#define LEN 100
int Top_Down_ Cut_Rod(int p[],int n) {
	/*自顶向下*/
	int r=0;
	int i;
	if(n == 0) {
		return 0;
	}
	for (i=1; (1) ;i++) {
		int tmp = p[i]+Top_Down_Cut_Rod(p,n-i);
		r=(r>=tmp)?r:tmp;
	}
	return r;
}
int Bottom_Up_Cut_Rod(int p[],int n) {
	/*自底向上*/
	int r[LEN]= {
		0
	}
	;
	int temp=0;
	int i,j;
	for (j=1;j<=n;j++) {
		temp=0;
		for (i=1; (2) ;i++) {
			temp= (3) ;
		}
		(4) ;
	}
	return r[n];
}

【问题:4.1】(8分)
根据说明,填充C代码中的空(1)~(4)。
【问题:4.2】(7分)
根据说明和C代码,算法采用的设计策略为(5)。
求解rn时,自顶向下方法的时间复杂度为(6);自底向上方法的时间复杂度为(7)(用O表示)。
2018年 上半年 下午试卷 案例
正确答案:
你的答案:
请先在App中激活(应用市场搜“软考真题”)
知识点:
试卷:
2018年 上半年 下午试卷 案例

笔记

请先在App中激活(应用市场搜“软考真题”)

2019-09-17


请先在App中激活(应用市场搜“软考真题”)

2019-05-15


请先在App中激活(应用市场搜“软考真题”)

2019-11-05


请先在App中激活(应用市场搜“软考真题”)

2019-05-25


请先在App中激活(应用市场搜“软考真题”)

2019-11-04


卡卡

请先在App中激活(应用市场搜“软考真题”)

2021-05-28


请先在App中激活(应用市场搜“软考真题”)

2019-05-12


答题卡
加油
纠错
得分:0